package com.fengye.algorithms.leecode.dp;

import java.util.*;

/**
 * @Author fengye
 * @Date 2023/4/24 5:46
 **/
public class WordBreakII140 {
    public static void main(String[] args) {
        String s = "appledappleatop";
        List<String> dict = Arrays.asList("app", "led", "a", "apple", "top");
        new WordBreakII140().wordBreak(s, dict).stream().forEach(System.out::println);
    }
    public List<String> wordBreak(String s, List<String> wordDict) {
        // 去重
        Set<String> dict = new HashSet<String>(wordDict);
        int len = s.length();
        // 第 1 步：动态规划计算是否有解
        boolean[] dp = new boolean[s.length()+1];
        List<Integer> flags = new ArrayList<>();
        flags.add(0);
        dp[0] = true;
        for(int i=1;i<=len;i++) {
            for(int j=0;j<i;j++) {
                // j已经包含在dick中，并且j-i字串也包含在dict中，那么dp[i]=true
                if(dp[j] && dict.contains(s.substring(j, i))) {
                    dp[i] = true;
                    flags.add(i);
                    break;
                }
            }
        }
        // 第二步回溯算法搜索所有符合条件的解
        List<String> res = new ArrayList<>();
        if (dp[len]) {
            Deque<String> path = new ArrayDeque<>();
            dfs(s, len, dict, dp, path, res);
            return res;
        }
        return res;
    }

    /**
     * s[0:len) 如果可以拆分成 wordSet 中的单词，把递归求解的结果加入 res 中
     *
     * @param s
     * @param len     长度为 len 的 s 的前缀子串
     * @param wordSet 单词集合，已经加入哈希表
     * @param dp      预处理得到的 dp 数组
     * @param path    从叶子结点到根结点的路径
     * @param res     保存所有结果的变量
     */
    private void dfs(String s, int len, Set<String> wordSet, boolean[] dp, Deque<String> path, List<String> res) {
        if (len == 0) {
            res.add(String.join(" ",path));
            return;
        }

        // 可以拆分的左边界从 len - 1 依次枚举到 0
        for (int i = len - 1; i >= 0; i--) {
            String suffix = s.substring(i, len);
            if (wordSet.contains(suffix) && dp[i]) {
                path.addFirst(suffix);
                dfs(s, i, wordSet, dp, path, res);
                path.removeFirst();
            }
        }
    }

}
